package com.leetcode.code;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Collections;
import java.util.Deque;
import java.util.List;

/**
 * Description:
 *
 * @author zkingcobra
 * Date: 2020/6/2 2:46 下午
 */
public class LeetCode0151Java {
    public static void main(String[] args) {

        Solution solution = new Solution();
        System.out.printf("开始:%s%n", solution.reverseWords3(" My name is  zhouyi"));
    }

    /**
     * 方法一：使用语言特性 : 1.split 2、Collections.reverse()  3、String.join() 我自己能想到这个
     * 方法二：自行编写对应的函数 1、取出多余空格 2、翻转所有字符 3、再次翻转单词字符
     * 方法三：双端队列 由于双端队列支持从队列头部插入的方法，因此我们可以沿着字符串一个一个单词处理，然后将单词压入队列的头部，再将队列转成字符串即可。
     */
    static private class Solution {
        /**
         * 使用语言特性
         *
         * @author zkingcobra
         */
        public String reverseWords(String s) {
            String content = s.trim();
            // 正则匹配连续的空白字符作为分隔符分割
            List<String> list = Arrays.asList(content.split("\\s+"));
            Collections.reverse(list);
            return String.join(" ", list);
        }

        public String reverseWords2(String s) {

            return "";
        }

        /**
         * 双端队列
         *
         * @author 官方
         */
        public String reverseWords3(String s) {
            // left right是非空字符串开始的位置
            int left = 0, right = s.length() - 1;
            // 去掉字符串开头的空白字符
            while (left <= right && s.charAt(left) == ' ') {
                ++left;
            }

            // 去掉字符串末尾的空白字符
            while (left <= right && s.charAt(right) == ' ') {
                --right;
            }

            Deque<String> d = new ArrayDeque();
            StringBuilder word = new StringBuilder();

            while (left <= right) {
                char c = s.charAt(left);
                if ((word.length() != 0) && (c == ' ')) {
                    // 将单词 push 到队列的头部
                    d.offerFirst(word.toString());
                    word.setLength(0);
                } else if (c != ' ') {
                    word.append(c);
                }
                ++left;
            }
            d.offerFirst(word.toString());

            return String.join(" ", d);
        }
    }
}
